/**
 * @author zlss
 * @date 2025/5/31
 * @description
 */
import java.util.Random;

public class SudokuEngine {
    private int[][] solution;
    private int[][] puzzle;
    private Random random;

    public SudokuEngine() {
        solution = new int[9][9];
        puzzle = new int[9][9];
        random = new Random();
    }

    public void generatePuzzle(Difficulty difficulty) {
        // 生成完整的解决方案
        solveEmptyBoard();

        // 根据难度移除数字
        int cellsToRemove = getCellsToRemove(difficulty);
        removeNumbers(cellsToRemove);

        // 复制解决方案和谜题
        copyBoard(solution, new int[9][9]);
        copyBoard(puzzle, new int[9][9]);
    }

    private void solveEmptyBoard() {
        // 清空棋盘
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                solution[row][col] = 0;
            }
        }

        // 使用回溯算法填充棋盘
        solveBoard(solution);
    }

    private boolean solveBoard(int[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == 0) {
                    // 尝试填入1-9
                    for (int num = 1; num <= 9; num++) {
                        if (isValidMove(board, row, col, num)) {
                            board[row][col] = num;

                            // 递归求解
                            if (solveBoard(board)) {
                                return true;
                            }

                            // 回溯
                            board[row][col] = 0;
                        }
                    }

                    return false; // 无法解决
                }
            }
        }

        return true; // 已解决
    }

    private boolean isValidMove(int[][] board, int row, int col, int number) {
        // 检查行
        for (int c = 0; c < 9; c++) {
            if (board[row][c] == number) {
                return false;
            }
        }

        // 检查列
        for (int r = 0; r < 9; r++) {
            if (board[r][col] == number) {
                return false;
            }
        }

        // 检查3x3宫格
        int boxRow = row / 3 * 3;
        int boxCol = col / 3 * 3;
        for (int r = boxRow; r < boxRow + 3; r++) {
            for (int c = boxCol; c < boxCol + 3; c++) {
                if (board[r][c] == number) {
                    return false;
                }
            }
        }

        return true;
    }

    private int getCellsToRemove(Difficulty difficulty) {
        switch (difficulty) {
            case EASY: return 30 + random.nextInt(5);
            case MEDIUM: return 35 + random.nextInt(5);
            case HARD: return 40 + random.nextInt(10);
            default: return 30;
        }
    }

    private void removeNumbers(int cellsToRemove) {
        // 复制解决方案到谜题
        copyBoard(solution, puzzle);

        // 移除单元格
        int removed = 0;
        while (removed < cellsToRemove) {
            int row = random.nextInt(9);
            int col = random.nextInt(9);

            if (puzzle[row][col] != 0) {
                int temp = puzzle[row][col];
                puzzle[row][col] = 0;

                // 检查是否有唯一解
                if (!hasUniqueSolution(puzzle)) {
                    puzzle[row][col] = temp; // 恢复单元格
                } else {
                    removed++;
                }
            }
        }
    }

    private boolean hasUniqueSolution(int[][] board) {
        int[][] tempBoard = new int[9][9];
        copyBoard(board, tempBoard);

        // 计算解的数量
        SolutionCounter counter = new SolutionCounter();
        countSolutions(tempBoard, counter);

        return counter.getCount() == 1;
    }

    private void countSolutions(int[][] board, SolutionCounter counter) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == 0) {
                    for (int num = 1; num <= 9; num++) {
                        if (isValidMove(board, row, col, num)) {
                            board[row][col] = num;
                            countSolutions(board, counter);
                            board[row][col] = 0;

                            // 如果已经找到2个解，就可以停止了
                            if (counter.getCount() >= 2) {
                                return;
                            }
                        }
                    }
                    return;
                }
            }
        }

        // 找到一个解
        counter.increment();
    }

    private void copyBoard(int[][] source, int[][] destination) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                destination[row][col] = source[row][col];
            }
        }
    }

    public int[][] getPuzzle() {
        return puzzle;
    }

    public int[][] getSolution() {
        return solution;
    }

    public int[] getHint(SudokuBoard currentBoard) {
        // 找到一个未填充的单元格
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (currentBoard.getValue(row, col) == 0) {
                    // 返回正确的数字
                    return new int[] {row, col, solution[row][col]};
                }
            }
        }

        return null; // 没有提示可用
    }

    // 用于计数解决方案的辅助类
    private static class SolutionCounter {
        private int count = 0;

        public void increment() {
            count++;
        }

        public int getCount() {
            return count;
        }
    }
}

